\documentclass[11pt, a4paper]{report}

\usepackage[utf8]{inputenc}
\usepackage[spanish]{babel}
\usepackage[pdftex]{graphicx}
\usepackage{fancyhdr}
\usepackage{array}
\usepackage{url}
\usepackage{a4wide}
\usepackage{caption}
\usepackage{color}
\usepackage{listings}
\usepackage{pdfpages}
\usepackage[pdftex,bookmarks=true]{hyperref}
\hypersetup{
    colorlinks,
    citecolor=black,
    filecolor=black,
    linkcolor=black,
    urlcolor=black
}

\definecolor{gray80}{gray}{.8}
\lstdefinestyle{consola}
        {
         basicstyle=\scriptsize\bf\ttfamily,
         backgroundcolor=\color{gray80},
         frame=Ltb,
         framerule=0pt,
         aboveskip=0.5cm,
         framextopmargin=3pt,
     framexbottommargin=3pt,
%      framexleftmargin=0.4cm,
     framesep=0pt,
     rulesep=.4pt,
     rulesepcolor=\color{black},
     tabsize=2
}

\renewcommand{\captionfont}{\footnotesize}
\renewcommand{\captionlabelfont}{\bfseries}

\usepackage[T1]{fontenc}
\usepackage{lmodern}
\renewcommand*\familydefault{\sfdefault}


\usepackage{color}
\usepackage{listings}

\definecolor{gray}{gray}{0.5}
\definecolor{green}{rgb}{0,0.5,0}


\newcommand{\imgdir}{./img}
\graphicspath{{\imgdir/}}

\newcommand{\cod}[1]{\texttt{\bfseries #1}}
\newcommand{\reg}[1]{\texttt{\bfseries #1}}
\newcommand{\n}{\texttt{\ensuremath{\backslash}n}}
\newcommand{\0}{\texttt{\ensuremath{\backslash}0}}

\def\thesection{\arabic{section}}

%parámetros para fbox
\setlength\fboxsep{15pt}
\setlength\fboxrule{0.5pt}

\title{66.20 Organización de computadoras}
\author{Verónica Bukaczewski \and Ariel George}
\date{\today}


\begin{document}
\include{caratula}

%Cabeceras y pies de página
\pagestyle{fancy}
\lhead{}
%\lhead{\fancyplain{}{Organizaci\'on de computadoras 66.20 - Turno Jueves}}
\chead{}
%\rhead{\fancyplain{}{Trabajo Pr\'actico 0}}
\rhead{}
\lfoot{\scriptsize{66.20 Organización de computadoras - Turno jueves\\Trabajo
práctico 1 - 1er cuatrimestre 2011\\Verónica Bukaczewski(86954), Ariel George
(88024)}}
\cfoot{}
\rfoot{\\\thepage}
\renewcommand{\headrulewidth}{0pt}

\setcounter{page}{2}

\newpage
\thispagestyle{empty}
\tableofcontents

\newpage
\section{Introducción}
 En el presente trabajo pr\'actico se busc\'o  familiarizarse con el conjunto de instrucciones MIPS y el concepto de ABI. Para ello, se realiz\'o un programa en lenguaje C que calcula el m\'inimo com\'un m\'ultiplo (mcm) y el m\'aximo com\'un divisor (MCD) entre dos n\'umeros. Pero,
 para que la implementaci\'on desarrollada provea un grado m\'inimo de portabilidad, se provee dos versiones de mcd y DCM, incluyendo una versi\'on MIPS32 y otra versi\'on C.

\section{Resolución del problema}
Los cálculos del máximo común divisor (mcd) y mínimo común múltiplo (mcm) se realizan en las funciones \cod{mcd} y \cod{mcm} respectivamente, declaradas en el archivo \cod{funciones.h}.
Estas funciones tienen una implementación en lenguaje \cod{C} válida para cualquier plataforma, y una implementación en \cod{assembly} para arquitectura MIPS32.

En ambos casos se emplea el algoritmo de Euclides implementado en forma recursiva para calcular el mcd; y el mcm se obtiene usando este cálculo como
\[
	\mathsf{mcm(a, b) = \frac{a \cdot b}{mcd(a,b)}}
\]

\subsection{Implementación MIPS32}
En ambas funciones, lo primero que se hace es crear el stack frame\footnote{El stack frame es una porción del stack que la función usa para almacenar variables locales, valores de registros que deben restaurarse, argumentos de la función, etc.}. 
Las funciones sólo reciben dos argumentos, por lo que no es necesario utilizar el stack para el pasaje de parámetros, sólo usa los registros \reg{a0} y \reg{a1}, por lo que el stack frame sólo contiene dos areas: \textit{general register save area} y \textit{argument building area} (debe tener como mínimo 16 bytes).

La \textit{general register save area} almacenará los registros \reg{gp}, \reg{fp} y \reg{ra} de 4 bytes cada uno por lo que requeriría 12 bytes. 
Sin embargo la ABI MIPS establece que el stack frame debe estar alineado a 8 bytes por lo que ocupará 16 bytes.
La \textit{argument building area} debe tener como mínimo 16 bytes.
En este caso ese espacio es suficiente porque sólo deben almacenarse los dos argumentos con los que se llama a las funciones\footnote{Esta sección del stack frame es la única que es escrita por el \textit{callee} y no por el \textit{caller}. Allí se guardan los argumentos con los que fue llamada la función. La función \cod{mcd} se llama a sí misma y \cod{mcm} llama a \cod{mcd}, por lo que en cualquier caso sólo es necesario guardar dos argumentos}.

Entonces el stack frame finalmente ocupará 32 bytes para ambas funciones, distribuidos como se muestra en la figura \ref{fig:stackframe}.

\begin{figure}[!ht]
\centering
	\fbox{\includegraphics[width=200pt]{stackframe}}
	\caption{Stack frame de las funciones \cod{mcd} y \cod{mcm}. Las direcciones a la izquierda están dadas como offsets respecto del stack pointer \reg{sp}.}
	\label{fig:stackframe}
\end{figure}

Antes de finalizar la ejecución de las funciones los valores almacenados se restauran a los registros correspondientes (\reg{gp}, \reg{fp}, \reg{ra}, \reg{a0} y \reg{a1}).


\subsubsection{Ejemplo de ejecución}
A continuación se muestran los stacks de las funciones \cod{mcd} y \cod{mcm} llamadas con los argumentos 256 y 192 (figuras \ref{fig:stackframe-mcd} y \ref{fig:stackframe-mcm}).
Se muestran los stack frames de las llamadas consecutivas de izquierda a derecha, indicando los valores almacenados en cada word (excepto cuando no sea necesario).
Las direcciones de cada word (los números a la izquierda) son hipotéticos, para indicar que el stack crece hacia las direcciones bajas de memoria y que los fragmentos representados son en realidad consecutivos.

Para el registro \reg{ra} se indican direcciones genéricas \emph{A1} y \emph{A2}, ya que no se sabe la dirección exacta del código.
Lo que sí sabemos es que será una dirección del \textit{text segment}, que se encuentra debajo del stack y de los datos dinámicos y estáticos.
Se usan esos valores para indicar que en el caso de \cod{mcd} (figura \ref{fig:stackframe-mcd}) la dirección de retorno es siempre la misma, porque son llamadas recursivas y por lo tanto se vuelve siempre a la misma porción del código.
En la figura \ref{fig:stackframe-mcm} la dirección de retorno almacenada en el primer stack frame es otra porque es la correspondiente al código de \cod{mcm}, mientras que el resto corresponde a \cod{mcd}. 


\begin{figure}[!ht]
\centering
	\fbox{\includegraphics[width=400pt]{stackframe-mcd}}
	\caption{Stack de la función \cod{mcd(25, 192)}. Los tres stack frames representados son consecutivos en memoria, con el correspondiente a la primera llamada más a la izquierda (el stack crece hacia las direcciones bajas de memoria). Las direcciones indicadas a la izquierda son únicamente de referencia. La dirección de retorno (\reg{ra}) también es hipotética.}
	\label{fig:stackframe-mcd}
\end{figure}

\begin{figure}[!ht]
\centering
	\fbox{\includegraphics[width=400pt]{stackframe-mcm}}
	\caption{Stack de la función \cod{mcm(25, 192)}. Los cuatro stack frames representados son consecutivos en memoria, con el correspondiente a la primera llamada más a la izquierda (el stack crece hacia las direcciones bajas de memoria). Las direcciones indicadas a la izquierda son únicamente de referencia. Las direcciones de retorno (\reg{ra}) también son hipotéticas.}
	\label{fig:stackframe-mcm}
\end{figure}

\section{Compilación}
Se provee un archivo Makefile para compilar el programa. 
Para compilar una versión del programa que utilice las implementaciones en \cod{C} de las funciones \cod{mcd} y \cod{mcm} ejecutar
\begin{lstlisting}[style=consola]
 $ make
\end{lstlisting}
Esto funciona tanto en el sistema operativo \textit{host} como en el \textit{guest} (NetBSD corriendo sobre el gxemul).

Para compilar la versión que usa las implementaciones en assembly MIPS32 de \cod{mcd} y \cod{mcm} ejecutar
\begin{lstlisting}[style=consola]
 $ make mips
\end{lstlisting}
Este comando funciona únicamente en el sistema operativo guest (NetBSD corriendo sobre el gxemul).
 
\section{Casos de prueba}
  \input{./corrida_de_pruebas.tex}

\section{Conclusiones}
  En el presente trabajo pr\'actico se aplicaron los conocimientos de el lenguaje \textit{assembly} aprendido en la materia
  as\'i como tambi\'en el manejo de las herramientas sobre las cuales hab\'iamos aprendido en el trabajo pr\'actico
  anterior. Al desarrollar nuestra primera aplicaci\'on con partes en \textit{assembly}, nos topamos con diversas dificultades,
  las cuales mediante la utilizaci\'on de herramientas de debugging como gdb, por ejemplo, pudimos ir solucionando hasta
  lograr el resultado deseado. Tambi\'en consideramos que pudimos aplicar los conocimientos relacionados a la {\bf ABI} 
  utilizada en la catedra para las llamadas a funciones. Concluimos que el trabajo pr\'actico nos pareci\'o de gran aprendizaje
  respecto de c\'omo volcar los conocimientos aprendidos en la materia a una aplicaci\'on desarrollada completamente en lenguaje
  \textit{assembly}.

\begin{thebibliography}{99}
	\bibitem{patterson}
		John L. Hennessy y David A. Patterson,
		\emph{\textbf{Computer architecture: a quantitative approach}}.
		Morgan Kaufmann Publishers,
		1990

  	\bibitem{mips}	
		\emph{\textbf{MIPS Assembly language programmer's guide}}.
        Silicon Graphics, Inc,	
		1992

    \bibitem{mips2}
        Daniel J. Ellard,
		\emph{\textbf{MIPS Assembly language programming}}.
		1994




\end{thebibliography}
%APENDICES
\appendix
\newpage
\chapter*{Enunciado}
\addcontentsline{toc}{section}{Enunciado}
\includepdf[pages=1-4, scale=0.9, pagecommand={\thispagestyle{empty}}]{../tp1-q1-2011.pdf}

\end{document}
